#pragma once

#include <istream>
#include "allocator.hpp"
#include "char_traits.hpp"
#include "functor.hpp"
#include "log_functor.hpp"
#include "reverse_iterator.hpp"

#ifdef _MSC_VER
#define True  , true
#define False , false
#else
#define True
#define False
#endif

namespace zuck
{
    template<typename StringType>
    class _StringConstIterator {
    private:
        using _Self = _StringConstIterator<StringType>;
    public:
        using value_type        = typename StringType::value_type;
        using pointer           = typename StringType::const_pointer;
        using reference         = typename StringType::const_reference;
        using difference_type   = typename StringType::difference_type;
        using iterator_category = zuck::random_access_iterator_tag;
    private:
        pointer _m_iter;
        pointer _m_first;
        pointer _m_last;
    public:
        explicit _StringConstIterator(pointer iter, pointer first, pointer last)noexcept
            : _m_iter(iter), _m_first(first), _m_last(last) {}

        _StringConstIterator(const _Self& other)
            : _m_iter(other._m_iter), _m_first(other._m_first)
            , _m_last(other._m_last) {}

        _StringConstIterator(_Self&& other)noexcept 
            : _m_iter(other._m_iter), _m_first(other._m_first)
            , _m_last(other._m_last) 
        {
            other._m_iter  = null;
            other._m_first = null;
            other._m_last  = null;
        }

        virtual ~_StringConstIterator()
        {
            _m_iter  = null;
            _m_first = null;
            _m_last  = null;
        }

        [[nodiscard]] pointer get_unwrapped()const noexcept
        { return _m_iter; }
        
        _Self& operator=(const _Self& other)
        {
            _m_iter  = other._m_iter;
            _m_first = other._m_first;
            _m_last  = other._m_last;
            return *this;
        }

        _Self& operator=(_Self&& other)noexcept
        {
            _m_iter  = other._m_iter;
            _m_first = other._m_first;
            _m_last  = other._m_last;
            other._m_iter  = null;
            other._m_first = null;
            other._m_last  = null;
            return *this;
        }

        [[nodiscard]] pointer operator->()const noexcept
        {
            if constexpr (debug_) {
                if (_m_iter >= _m_last || _m_iter < _m_first) {
                    debug_log::derror(zuck::SEG_WrongIter, 
                        "Segmentfault: invalid iterator");
                }
            }
            return _m_iter;
        }

        [[nodiscard]] reference operator*()const noexcept
        {
            if constexpr (debug_) {
                if (_m_iter >= _m_last || _m_iter < _m_first) {
                    debug_log::derror(zuck::SEG_WrongIter,
                        "Segmentfault: invalid iterator");
                }
            }
            return *_m_iter;
        }
        
        _Self& operator++()noexcept
        {
            ++_m_iter;
            return *this;
        }

        [[nodiscard]] _Self operator++(int)noexcept
        {
            auto _Tmp = *this;
            ++_m_iter;
            return _Tmp;
        }

        _Self& operator+=(difference_type const _Offset)noexcept
        {
            if constexpr (debug_) {
                if (_m_iter + _Offset >= _m_last) {
                    debug_log::derror(zuck::SEG_OutofRange,
                        "Segmentfault: invalid offset");
                }
            }
            _m_iter += _Offset;
            return *this;
        }

        [[nodiscard]] _Self operator+(difference_type const _Offset)const noexcept
        {
            if constexpr (debug_) {
                if (_m_iter + _Offset >= _m_last) {
                    debug_log::derror(zuck::SEG_OutofRange,
                        "Segmentfault: invalid offset");
                }
            }
            auto _Tmp = *this;
            return _Tmp += _Offset;
        }

        [[nodiscard]] reference operator[](difference_type const _Offset)const noexcept
        { return *(*this + _Offset); }

        _Self& operator--()noexcept
        {
            --_m_iter;
            return *this;
        }

        [[nodiscard]] _Self operator--(int)noexcept
        {
            auto _Tmp = *this;
            --_m_iter;
            return _Tmp;
        }

        _Self& operator-=(difference_type const _Offset)noexcept
        {
            if constexpr (debug_) {
                if (_m_iter - _Offset < _m_first) {
                    debug_log::derror(zuck::SEG_OutofRange,
                        "Segmentfault: invalid offset");
                }
            }
            _m_iter -= _Offset;
            return *this;
        }

        [[nodiscard]] _Self operator-(difference_type const _Offset)const noexcept
        {
            auto _Tmp = *this;
            return _Tmp -= _Offset;
        }

        [[nodiscard]] inline difference_type operator-(const _Self& other)const noexcept
        { return static_cast<difference_type>(_m_iter - other._m_iter); }

        [[nodiscard]] inline difference_type operator-(pointer ptr)const noexcept
        { return static_cast<difference_type>(_m_iter - ptr); }

        [[nodiscard]] inline bool operator==(_Self const& other)const noexcept
        { return static_cast<bool>(_m_iter == other._m_iter); }

        [[nodiscard]] inline bool operator!=(_Self const& other)const noexcept
        { return static_cast<bool>(_m_iter != other._m_iter); }

        [[nodiscard]] inline bool operator<(_Self const& other)const noexcept
        { return static_cast<bool>(_m_iter < other._m_iter); }

        [[nodiscard]] inline bool operator<=(_Self const& other)const noexcept
        { return static_cast<bool>(_m_iter <= other._m_iter); }

        [[nodiscard]] inline bool operator>(_Self const& other)const noexcept
        { return static_cast<bool>(_m_iter > other._m_iter); }

        [[nodiscard]] inline bool operator>=(_Self const& other)const noexcept
        { return static_cast<bool>(_m_iter >= other._m_iter); }
    };

    template<typename StringType>
    class _StringIterator : public _StringConstIterator<StringType> {
    private:
        using _Self = _StringIterator<StringType>;
        using _Base = _StringConstIterator<StringType>;
    public:
        using value_type        = typename _Base::value_type;
        using pointer           = value_type*;
        using reference         = value_type&;
        using difference_type   = typename _Base::difference_type;
        using iterator_category = random_access_iterator_tag;
    public:
        explicit _StringIterator(pointer iter = null, pointer first = null, pointer last = null)noexcept
            : _Base(iter, first, last) {}

        _StringIterator(_Self const& other) : _Base(other) {}

        _StringIterator(_Self&& other)noexcept : _Base(zuck::move(other)) {}

        _Self& operator=(const _Self& other)
        {
            _Base::operator=(other);
            return *this;
        }

        _Self& operator=(_Self&& other)noexcept
        {
            _Base::operator=(zuck::move(other));
            return *this;
        }

        [[nodiscard]] inline reference operator*()noexcept
        { return const_cast<reference>(_Base::operator*()); }

        [[nodiscard]] inline pointer operator->()noexcept
        { return const_cast<pointer>(_Base::operator->()); }

        inline _Self& operator++()noexcept
        {
            _Base::operator++();
            return *this;
        }

        [[nodiscard]] inline _Self operator++(int)noexcept
        {
            auto _Tmp = *this;
            _Base::operator++();
            return _Tmp;
        }

        inline _Self& operator+=(const difference_type _Offset)noexcept
        {
            _Base::operator+=(_Offset);
            return *this;
        }

        [[nodiscard]] inline _Self operator+(const difference_type _Offset)noexcept
        {
            auto _Tmp = *this;
            return _Tmp += _Offset;
        }

        [[nodiscard]] inline reference operator[](difference_type const _Offset)noexcept
        { return const_cast<reference>(_Base::operator[](_Offset)); }

        inline _Self& operator--()noexcept
        {
            _Base::operator--();
            return *this;
        }

        [[nodiscard]] inline _Self operator--(int)noexcept
        {
            auto _Tmp = *this;
            _Base::operator--();
            return _Tmp;
        }

        inline _Self& operator-=(const difference_type _Offset)noexcept
        {
            _Base::operator-=(_Offset);
            return *this;
        }

        [[nodiscard]] inline _Self operator-(const difference_type _Offset)const noexcept
        {
            auto _Tmp = *this;
            return _Tmp -= _Offset;
        }

        [[nodiscard]] inline difference_type operator-(const _Self& other)const noexcept
        { return _Base::operator-(other); }

        [[nodiscard]] inline difference_type operator-(const value_type* ptr)const noexcept
        { return _Base::operator-(ptr); }
    };


    template<typename CharType, 
        typename Traits = zuck::_CharTraits<CharType>, 
        typename Alloc = zuck::allocator<CharType>
    >
    class String {
    private:
        using _Self     = String<CharType, Traits, Alloc>;
        using _Alty_tts = allocator_traits<Alloc>;
        using _Char_tts = Traits;
    public:
        using value_type      = typename _Alty_tts::value_type;
        using pointer         = typename _Alty_tts::pointer;
        using const_pointer   = typename _Alty_tts::const_pointer;
        using size_type       = typename _Alty_tts::size_type;
        using reference       = typename _Alty_tts::reference;
        using const_reference = typename _Alty_tts::const_reference;
        using difference_type = typename _Alty_tts::difference_type;
        using allocator_type  = typename _Alty_tts::allocator_type;
    public:
        using iterator               = _StringIterator<_Self>;
        using const_iterator         = _StringConstIterator<_Self>;
        using reverse_iterator       = zuck::reverse_iterator<iterator>;
        using const_reverse_iterator = zuck::reverse_iterator<const_iterator>;
    private:
        pointer _m_start;
        pointer _m_last;
        pointer _m_end;
        Alloc   alloc;
    public:
        static auto constexpr npos = static_cast<size_type>(-1);
    public:
        explicit String() : _m_start(), _m_last(), _m_end(), alloc(Alloc{}) {}

        String(const CharType* const _Data)
            : _m_start(), _m_last(), _m_end(), alloc(Alloc{})
        {
            auto const _Newsize = Traits::strlen(_Data);
            __construct_range(_Data, _Data + _Newsize);
        }

        String(std::initializer_list<CharType> data)
            : _m_start(), _m_last(), _m_end(), alloc(Alloc{})
        {
            __construct_range(data.begin(), data.end());
        }

        explicit String(const size_type _Newsize, const CharType val)
            : _m_start(), _m_last(), _m_end()
        {
            __construct_n(_Newsize, val);
        }

        template<typename InputIterator,
            zuck::enable_if_t<zuck::is_iterator_v<InputIterator>, int> = 0>
        explicit String(InputIterator first, InputIterator last)
            : _m_start(), _m_last(), _m_end(), alloc(Alloc{})
        {
            __construct_range(first, last);
        }

        template<typename InputIterator,
            zuck::enable_if_t<zuck::is_iterator_v<InputIterator>, int> = 0>
        explicit String(InputIterator first, InputIterator last, Alloc al = Alloc{})
            : _m_start(), _m_last(), _m_end(), alloc(al)
        {
            __construct_range(first, last);
        }

        String(const String& other)
            : _m_start(), _m_last(), _m_end(), alloc(other.alloc)
        {
            __construct_range(other.begin(), other.end());
        }

        String(String&& other)noexcept
            : alloc(other.alloc)
        {
            __move_construct(zuck::forward<String>(other));
        }

        ~String() { __destroy(); }

        [[nodiscard]] reference at(const size_type _Idx)
        {
            if constexpr (debug_) {
                if (out_of_range(_Idx, size())) {
                    throw std::out_of_range{};
                }
            }
            return *(_m_start + _Idx);
        }

        [[nodiscard]] const_reference at(const size_type _Idx)const
        {
            if constexpr (debug_) {
                if (out_of_range(_Idx, size())) {
                    throw std::out_of_range{};
                }
            }
            return *(_m_start + _Idx);
        }

        void assign(const size_type _Newsize, const CharType& val)
        {
            auto const _Oldcapacity = capacity();
            if (_Newsize > _Oldcapacity) {
                __verify_size(_Newsize);
                alloc.deallocate(_m_start, _Oldcapacity);
                _m_start = alloc.allocate(_Newsize);
                _m_last  = _m_start + _Newsize;
                _m_end   = _m_start + _Newsize;
                __fill_range(_m_start, _m_last, val);
                return;
            }
            auto const _Oldsize = size();
            if (_Newsize > _Oldsize) {
                _m_last += (_Newsize - _Oldsize);
                __fill_range(_m_start, _m_last, val);
                return;
            }
            _m_last -= (_Oldsize - _Newsize);
            __fill_range(_m_start, _m_last, val);
        }

        void assign(std::initializer_list<CharType> data)
        {
            __assign_range(data.begin(), data.end());
        }

        template<typename InputIerator, 
            zuck::enable_if_t<zuck::is_iterator_v<InputIerator>, int> = 0>
        void assign(InputIerator first, InputIerator last)
        {
            __assign_range(first, last);
        }

        void assign(CharType const* const _Str)
        {
            auto const _Newsize = Traits::length(_Str);
            __assign_range(_Str, _Str + _Newsize);
        }

        bool append(CharType const* const _Data)
        {
            auto const _Othersize = Traits::length(_Data);
            auto const _Oldsize   = size();
            auto const _Max       = max_size();
            auto const _Newsize   = _Othersize + _Oldsize;

            __verify_size(_Oldsize);
            auto const _Oldcapacity = capacity();
            if (_Newsize > _Oldcapacity) {
                reserve(_Newsize);
            }
            zuck::fill(_Data, _Data + _Othersize, _m_last, _m_last + _Othersize);
            _m_last += _Othersize;
            return true;
        }

        void clear()
        {
            _Alty_tts::destruct_range(_m_start, _m_last);
            _m_last = _m_start;
        }

        [[nodiscard]] int compare(String const& other)const noexcept
        { return __compare_str(other.data()); }

        [[nodiscard]] int compare(const CharType* const _Elem)const noexcept
        { return __compare_str(_Elem); }

        [[nodiscard]] inline pointer data()const noexcept
        { return _m_start; }

        [[nodiscard]] inline reference front()noexcept
        { return *_m_start; }

        [[nodiscard]] inline const_reference front()const noexcept
        { return *_m_start; }

        [[nodiscard]] inline reference back()noexcept
        { return *(_m_last - 1); }

        [[nodiscard]] inline const_reference back()const noexcept
        { return *(_m_last - 1); }

        inline void pop_back()noexcept
        {
            _Alty_tts::destruct(*_m_last);
            --_m_last;
        }

        inline void push_back(const CharType& _Ch)
        { __push_elem(_Ch); }

        inline void push_back(CharType&& _Ch)
        { __push_elem(zuck::move(_Ch)); }

        inline void resize(size_type const _Newsize)
        { __resize(_Newsize, CharType{}); }

        inline void resize(size_type const _Newsize, CharType const _Ch)
        { __resize(_Newsize, _Ch); }

        inline void reserve(size_type const _new_capacity)
        {
            if (_new_capacity > capacity()) {
                if (_new_capacity > max_size()) {
                    debug_log::derror(SegmentCase::SEG_LengthTooLong, 
                        "Segmentfault: vector length too long !");
                }
                __realloc(_new_capacity);
            }
        }

        inline String& replace(size_type const _Off, size_type _Count, const CharType* const _Elem)
        {
            __replace_aux(_Off, _Count, _Elem);
            return *this;
        }

        inline String& replace
        (size_type const _Off, size_type const _Count, size_type const _N, CharType const& _Elem)
        {
            pointer _Data = alloc.allocate(_N + 1);
            zuck::fill(_Data, _Data + _N, _Elem);
            _Data[_N] = CharType{};
            __replace_aux(_Off, _Count, _Data);
            alloc.deallocate(_Data, _N + 1);
            return *this;
        }

        inline String& replace(iterator begin, iterator end, CharType const* const _Elem)
        {
            auto* _Begin = begin.get_unwrapped();
            auto* _End = end.get_unwrapped();
            auto const _Off = _Begin - _m_start;
            auto const _Count = _End - _Begin;
            __replace_aux(_Off, _Count, _Elem);
            return *this;
        }

        [[nodiscard]] inline String substr(size_type const _Start, size_type const _Length)
        {
            auto const _Size = size();
            if (_Start >= _Size) {
                return _Self{};
            }
            auto const _FinalPos = (_m_start + _Start + _Length >= _m_last ? _Size : _Start + _Length);
            String<CharType, Alloc> _Res(_FinalPos, CharType{});
            zuck::fill(_m_start + _Start, _m_start + _FinalPos, _Res.begin(), _Res.end());
            return _Res;
        }

        inline void swap(String& other)noexcept
        {
            if (*this != other) {
                auto _Tmp = zuck::move(*this);
                *this = zuck::move(other);
                other = zuck::move(_Tmp);
            }
        }

        inline String& erase(const size_type _Off = 0)
        {
            __check_offset(_Off);
            auto const _Size = size();
            _m_last -= (_Size - _Off);
            for (CharType* __d = _m_start; __d != _m_last; ++__d) {
                *__d = CharType{};
            }
            return *this;
        }

        [[nodiscard]] inline pointer c_str()noexcept
        { return _m_start; }

        [[nodiscard]] inline const_pointer c_str()const noexcept
        { return _m_start; }

        [[nodiscard]] inline size_type capacity()const noexcept
        { return static_cast<size_type>(_m_end - _m_start); }

        [[nodiscard]] inline size_type size()const noexcept
        { return static_cast<size_type>(_m_last - _m_start); }

        [[nodiscard]] inline size_type max_size()const noexcept
        { return _Alty_tts::max_size(); }

        [[nodiscard]] inline size_type unused_capacity()const noexcept
        { return static_cast<size_type>(_m_end - _m_last); }

        [[nodiscard]] inline bool empty()const noexcept
        { return static_cast<bool>(_m_last == _m_start); }

        [[nodiscard]] inline bool no_unused()const noexcept
        { return static_cast<bool>(_m_last == _m_end); }

        [[nodiscard]] inline iterator begin()noexcept
        { return iterator(_m_start, _m_start, _m_last); }

        [[nodiscard]] inline iterator end()noexcept
        { return iterator(_m_last, _m_start, _m_last); }

        [[nodiscard]] inline const_iterator begin()const noexcept
        { return const_iterator(_m_start, _m_start, _m_last); }

        [[nodiscard]] inline const_iterator end()const noexcept
        { return const_iterator(_m_last, _m_start, _m_last); }

        [[nodiscard]] inline const_iterator cbegin()const noexcept
        { return const_iterator(_m_start, _m_start, _m_last); }

        [[nodiscard]] inline const_iterator cend()const noexcept
        { return const_iterator(_m_last, _m_start, _m_last); }

        [[nodiscard]] inline reverse_iterator rbegin()const noexcept
        { return reverse_iterator(_m_last - 1, _m_start, _m_last); }

        [[nodiscard]] inline reverse_iterator rend()const noexcept
        { return reverse_iterator(_m_start - 1, _m_start, _m_last); }

        [[nodiscard]] inline const_reverse_iterator crbegin()const noexcept
        { return const_reverse_iterator(_m_last - 1, _m_start, _m_last); }

        [[nodiscard]] inline const_reverse_iterator crend()const noexcept
        { return const_reverse_iterator(_m_start - 1, _m_start, _m_last); }

        [[nodiscard]] inline size_type
        find(const CharType& ch, size_type off = 0)const noexcept
        {
            return __find_first_char_with(ch, off, zuck::equal_to<void>{});
        }

        [[nodiscard]] inline size_type
        find(const CharType* const data, size_type off = 0)const noexcept
        {
            return __find_first_str(data, off);
        }
        
        [[nodiscard]] inline size_type
        find_first_of
        (CharType const& ch, size_type off = 0)const noexcept
        {
            return __find_first_char_with(ch, off, zuck::equal_to<void>{});
        }

        [[nodiscard]] inline size_type
        find_first_of
        (CharType const* const data, size_type off = 0)const noexcept
        {
            return __find_first_str(data, off);
        }

        [[nodiscard]] inline size_type
        find_first_not_of
        (CharType const& ch, size_type off = 0)const noexcept
        {
            return __find_first_char_with(ch, off, zuck::not_equal_to<void>{});
        }

        [[nodiscard]] inline size_type
        find_first_not_of
        (CharType const* const data, size_type off = 0)const noexcept
        {
            return (__find_first_str(data, off) == npos) ? 0 : npos;
        }

        [[nodiscard]] inline size_type
        find_last_of
        (CharType const& ch, size_type off = 0)const noexcept
        {
            return __find_last_char_with(ch, off, zuck::equal_to<void>{});
        }

        [[nodiscard]] inline size_type
        find_last_of
        (CharType const* const data, size_type off = npos)const noexcept
        {
            return __find_last_str(data, Traits::strlen(data), off);
        }

        [[nodiscard]] inline size_type
        find_last_not_of
        (CharType const& ch, size_type off = npos)const noexcept
        {
            return __find_last_char_with(ch, off, zuck::not_equal_to<void>{});
        }

        [[nodiscard]] inline size_type
        find_last_not_of
        (CharType const* const data, size_type off = npos)const noexcept
        {
            return __find_last_not_of_aux(data, off);
        }

        [[nodiscard]] inline size_type
        rfind(CharType const* const data, size_type off = npos)const noexcept
        {
            return __find_last_str(data, Traits::strlen(data), off);
        }

        static inline void reverse(iterator begin, iterator end)
        {
            for (; begin != end; ++begin, --end) {
                zuck::iter_swap(begin, end);
            }
        }

        inline String& operator=(String const& other)
        {
            __copy_contruct(other);
            return *this;
        }

        inline String& operator=(String&& other)noexcept
        {
            __move_construct(zuck::move(other));
            return *this;
        }

        [[nodiscard]] inline CharType& operator[](const size_type _Idx)noexcept
        {
            if constexpr (debug_) {
                __verify_idx(_Idx, size());
            }
            return *(_m_start + _Idx);
        }

        [[nodiscard]] inline CharType const& operator[](const size_type _Idx)const noexcept
        {
            if constexpr (debug_) {
                __verify_idx(_Idx, size());
            }
            return *(_m_start + _Idx);
        }

        [[nodiscard]] inline bool operator==(String const& other)const noexcept
        { return static_cast<bool>(__compare_str(other.data()) == 0); }

        [[nodiscard]] inline bool operator!=(String const& other)const noexcept
        { return static_cast<bool>(__compare_str(other.data()) != 0); }

        [[nodiscard]] inline bool operator<(String const& other)const noexcept
        { return static_cast<bool>(__compare_str(other.data()) < 0); }

        [[nodiscard]] inline bool operator>(String const& other)const noexcept
        { return static_cast<bool>(__compare_str(other.data()) > 0); }

        [[nodiscard]] inline bool operator<=(String const& other)const noexcept
        { return static_cast<bool>(__compare_str(other.data()) <= 0); }

        [[nodiscard]] inline bool operator>=(String const& other)const noexcept
        { return static_cast<bool>(__compare_str(other.data()) >= 0); }

    private:
        template<typename InputIterator>
        void __assign_range(InputIterator first, InputIterator last)
        {
            auto _Next = _m_start;
            auto _First = first;
            auto const _Last = last;
            auto const _Newsize = static_cast<size_type>(_Last - _First);
            auto const _Oldcapacity = capacity();
            auto const _Max = max_size();
            if (_Max < _Newsize) {
                debug_log::derror(SegmentCase::SEG_LengthTooLong, 
                    "vector length too long !");
            }
            if (_Oldcapacity < _Newsize) {
                alloc.deallocate(_m_start, _Oldcapacity);
                _m_start = alloc.allocate(_Newsize);
                _m_end = _m_last = _m_start + _Newsize;
                zuck::fill(_First, _Last, _m_start, _m_last);
                return;
            }
            for (; _First != _Last && _Next != _m_last; ++_First, ++_Next) {
                *_Next = *_First;
            }
            _Alty_tts::destruct_range(_Next, _m_last);
            _m_last = _Next;
            for (; _First != _Last; ++_First) {
                __push_elem(*_First);
            }
        }

        [[nodiscard]] size_type __calc_capacity(const size_type _NewCapacity)
        {
            auto const _Oldcapacity = capacity();
            auto const _Max = max_size();

            if (_NewCapacity > _Max - _Oldcapacity) {
                return _Max;
            }
            auto const calc = _Oldcapacity < 35 ?
                (_Oldcapacity << 1) : (_Oldcapacity + (_Oldcapacity >> 1));
            if (_NewCapacity < calc) {
                return calc;
            }
            return _NewCapacity;
        }

        [[nodiscard]] int __compare_str(CharType const* _Elem)const noexcept
        {
            auto* _Proxy = _m_start;

            for (; *_Proxy && (*_Proxy == *_Elem); ++_Proxy, ++_Elem);
            int ans = *_Proxy - *_Elem;

            if (ans < 0) {
                return -1;
            }
            else if (ans > 0) {
                return 1;
            }
            return 0;
        }

        void __construct_n(CharType elem, size_type const _size)
        {
            __verify_size(_size);
            auto const _FinalSize = (_size <= 15 ? 15 : (_size + (_size >> 1)));
            __verify_size(_FinalSize);
            _m_start = alloc.allocate(_FinalSize);
            _m_end   = _m_start + _FinalSize;
            _m_last  = _m_start + _size;
            __fill_n(_m_start, _m_last, elem);
        }
        
        void __fill_n(pointer Begin, pointer End, CharType _Ch)
        {
            for (; Begin != End; ++Begin) {
                _Alty_tts::construct(Begin, _Ch);
            }
        }

        template<typename Iterator>
        void __construct_range(Iterator first, Iterator last)
        {
            auto const _Newsize = zuck::distance(first, last);
            __verify_size(_Newsize);

            auto const _FinalSize = (_Newsize < 35 ? (_Newsize << 1) : (_Newsize + (_Newsize >> 1)));
            _m_start = alloc.allocate(_FinalSize);
            _m_end   = _m_start + _FinalSize;
            _m_last  = _m_start + _Newsize;
            zuck::fill(first, last, _m_start, _m_last);
        }

        void __destroy()
        {
            auto const _capacity = capacity();
            alloc.deallocate(_m_start, _capacity);
            _m_start = null;
            _m_last  = null;
            _m_end   = null;
        }

        void __copy_contruct(const String& other)
        {
            if (*this == other) {
                return;
            }
            if (!empty()) {
                __destroy();
            }
            __construct_range(other.begin(), other.end(), other.size());
        }

        template<typename Iter, typename Valty>
        void __fill_range(Iter _First, Iter _Last, Valty val)
        {
            __verify_range(_First, _Last);
            for (; _First != _Last; ++_First) {
                _Alty_tts::construct(_First, val);
            }
        }

        template<typename Iter1, typename Iter2>
        void __fill_range(Iter1 _Srcfirst, Iter1 _Srclast, Iter2 _DesBegin, Iter2 _DesEnd)
        {
            __verify_range(_Srcfirst, _Srclast);
            __verify_range(_DesBegin, _DesEnd);

            auto _First1 = zuck::move(_Srcfirst);
            auto const _Last1 = zuck::move(_Srclast);
            auto _First2 = zuck::move(_DesBegin);
            auto const _Last2 = zuck::move(_DesEnd);

            for (;	_First1 != _Last1 && _First2 != _Last2;
                ++_First1, ++_First2) {
                *_First2 = *_First1;
            }
        }

        void __move_construct(String&& other)noexcept
        {
            if (!empty()) {
                __destroy();
            }
            _m_start = other._m_start;
            _m_last  = other._m_last;
            _m_end   = other._m_end;
            other._m_start = null;
            other.__laat  = null;
            other._m_end  = null;
            _Alty_tts::destruct(other.alloc);
        }

        void __realloc(size_type const _NewCapacity)
        {
            auto const _OldCapacity = capacity();
            auto const _Max = max_size();
            if (_OldCapacity == _NewCapacity) {
                return;
            }
            if (_OldCapacity < _NewCapacity) {
                __verify_size(_NewCapacity);
                auto const _Oldsize = size();
                auto* _Proxy = _m_start;
                _m_start = alloc.allocate(_NewCapacity);
                _m_end = zuck::address_of(*(_m_start + (_NewCapacity - 1))) + 1;
                _m_last = _m_start + _Oldsize;
                __fill_range(_m_start, _m_end, CharType{});
                __fill_range(_Proxy, _Proxy + _Oldsize, _m_start, _m_last);
                alloc.deallocate(_Proxy, _OldCapacity);
                return;
            }
        }

        void __sequence_expand_()
        {
            auto* _Proxy = _m_start;
            auto const _OldCapacity = capacity();
            auto const _NewCapacity = (_OldCapacity < 50000 ?
                (_OldCapacity << 1) :
                (_OldCapacity + (_OldCapacity >> 1)));

            __verify_size(_NewCapacity);
            _m_start = alloc.allocate(_NewCapacity);
            __fill_range(_Proxy, _Proxy + _OldCapacity, _m_start, _m_start + _OldCapacity);
            _Alty_tts::destruct_range(_Proxy, _Proxy + _OldCapacity);
            alloc.deallocate(_Proxy, _OldCapacity);
            _m_end  = zuck::address_of(_m_start[_NewCapacity - 1]) + 1;
            _m_last = zuck::address_of(_m_start[_OldCapacity - 1]) + 1;
        }

        void __resize(size_type const _new, CharType const& val)
        {
            auto const _Oldsize = size();
            auto const _Oldcapacity = capacity();
            auto const _Max = max_size();
            if (_new > _Max) {
                debug_log::derror(SegmentCase::SEG_LengthTooLong, 
                    "vector length too long !");
            }
            else if (_new > _Oldcapacity) {
                auto* _Proxy = _m_start;
                _m_start = alloc.allocate(_new);
                __fill_range(_Proxy, _Proxy + _Oldsize, _m_start, _m_start + _Oldsize);
                __fill_range(_m_start + _Oldsize, _m_start + _new, val);
                _m_last = _m_end = _m_start + _new;
                alloc.deallocate(_Proxy, _Oldcapacity);
                return;
            }
            _m_last += _new - _Oldsize;
            if (_Oldsize < _new) {
                __fill_range(_m_start + _Oldsize, _m_last, val);
                return;
            }
        }

        void __push_elem(CharType const& _Ch)
        {
            if (!no_unused()) {
                *(_m_last++) = _Ch;
                return;
            }
            if (!_m_start) {
                __init(_Ch);
                return;
            }
            __sequence_expand_();
            *(_m_last++) = _Ch;
        }

        void __replace_aux(size_type const _Off, size_type _Count, CharType const* const _Elem)
        {
            __check_offset(_Off);
            auto const _Oldsize = size();
            auto const _Len = Traits::strlen(_Elem);
            if (_m_start + _Off + _Count > _m_last) {
                _Count -= ((_m_start + _Off + _Count) - _m_last);
            }
            auto const _Oldcapacity = capacity();
            auto const _Max = max_size();
            if (_Len > _Count) {
                if (_Oldsize + _Len > _Oldcapacity) {
                    __realloc(_Oldcapacity + _Len);
                }
            }
            auto* _UnreplaceBgn = _m_start + _Off + _Count;
            auto const _UnreplaceCount = (_m_last - _UnreplaceBgn);
            pointer _TmpBuffer = (_UnreplaceCount > 0 ? alloc.allocate(_UnreplaceCount) : null);

            if (_TmpBuffer) {
                zuck::fill(_UnreplaceBgn, _m_last, _TmpBuffer, _TmpBuffer + _UnreplaceCount);
            }
            zuck::fill(_Elem, _Elem + _Len, _m_start + _Off, _m_start + _Off + _Len);
            (_Len > _Count && _Len > 0) ? (_m_last += (_Len - _Count)) : (_m_last -= (_Count - _Len));

            if (_TmpBuffer) {
                zuck::fill(_TmpBuffer, _TmpBuffer + _UnreplaceCount, _m_start + _Off + _Len, _m_last);
                alloc.deallocate(_TmpBuffer, _UnreplaceCount);
            }
        }

        template<typename _Equal>
        [[nodiscard]] size_type __find_first_char_with(CharType const& ch, size_type off, _Equal _Pr)
        {
            for (; _m_start + off < _m_last; ++off) {
                if (_Pr(_m_start[off], ch)) {
                    return off;
                }
            }
            return static_cast<zuck::size_t>(-1);
        }

        template<typename _Equal>
        [[nodiscard]] size_type __find_last_char_with(CharType const& ch, size_type off, _Equal _Pr)const noexcept
        {
            size_type res = 0;
            auto const _Size = size();
            off = (off == npos) ? _Size - 1 : off;
            for (; _m_start + off >= _m_start; --off) {
                if (_Pr(_m_start[off], ch)) {
                    res = off;
                }
            }
            return !res ? static_cast<zuck::size_t>(-1) : res;
        }

        template<typename Iter>
        void __verify_range(Iter first, Iter last)noexcept
        {
            if (first >= last) {
                debug_log::derror(SegmentCase::SEG_OutofRange, 
                    "iterator range is invalid !");
            }
        }

        void __verify_idx(size_type const _Idx, size_type const _Size)noexcept
        {
            if (_Idx >= _Size) {
                debug_log::derror(zuck::SEG_OutofRange, 
                    "Segmentfault: subscript out of range !");
            }
        }

        void __verify_size(size_type _NewCapacity)noexcept
        {
            auto const _Max = max_size();
            if (_NewCapacity > _Max) {
                debug_log::derror(zuck::SEG_LengthTooLong, 
                    "String length too long !");
            }
        }

        [[nodiscard]] size_type
        __find_first_str(const CharType* const des, size_type off)const
        {
            int code[256] = { 0 }, n = 0;
            for (int i = 0; des[i]; ++i, ++n) {
                code[des[i]] |= (1 << i);
            }
            int p = 0;
            auto const _Size = size();
            for (; off < _Size; ++off)
            {
                p = (p << 1 | 1) & code[_m_start[off]];
                if (p & (1 << (n - 1))) {
                    return off - n + 1;
                }
            }
            return static_cast<zuck::size_t>(-1);
        }

        [[nodiscard]] size_type
        __find_last_str(const CharType* const des, const size_type _Deslen, size_type off)const
        {
            auto const _Size = size();
            size_type _Res   = npos;
            off = (off == npos) ? (_Size - 1) : off;
            for (; off > 0 && off < _Size; off -= _Deslen) {
                if ((_Res = __find_first_str(des, off)) != npos) {
                    return _Res;
                }
            }
            return _Res;
        }

        [[nodiscard]] size_type __find_last_not_of_aux(CharType const* const des, size_type off)const
        {
            auto const len = Traits::strlen(des);
            auto _Res = __find_last_str(des, off);
            return (_Res != npos) ? (_Res + len) : npos;
        }

        void __init(const CharType& _Ch)
        {
            _m_start = alloc.allocate(15);
            _m_last = _m_start + 1;
            _m_end  = _m_start + 15;
            *_m_start = _Ch;
        }

        void __check_offset(size_type const _Offset)
        {
            if (_m_start + _Offset > _m_last) {
                debug_log::derror(::zuck::SEG_OutofRange, 
                    "Segmentfault: offset out of range !");
            }
        }
    };

    template<typename CharType, typename _Traits, typename Alloc>
    // referenced from source code
    ::std::basic_istream<CharType, _Traits>& operator>>
    (::std::basic_istream<CharType, _Traits>& _In, String<CharType, _Traits, Alloc>& _Str)
    {
        using _Istream = ::std::basic_istream<CharType, _Traits>;
        using _Ctype   = typename _Istream::_Ctype;
        using _String  = String<CharType, _Traits, Alloc>;
        using _Sizet   = typename _String::size_type;

        typename _Istream::iostate _State = _Istream::goodbit;
        bool changed                      = false;
        const typename _Istream::sentry _Ok(_In);

        if (_Ok) {
            const _Ctype& _Ctype_fac = ::std::use_facet<_Ctype>(_In.getloc());
            _Str.erase();
            try {
                _Sizet _Size;
                if (0 < _In.width() && static_cast<_Sizet>(_In.width()) < _Str.max_size()) {
                    _Size = static_cast<_Sizet>(_In.width());
                }
                else {
                    _Size = _Str.max_size();
                }

                typename _Traits::int_type _Meta = _In.rdbuf()->sgetc();

                for (; 0 < _Size; --_Size, _Meta = _In.rdbuf()->snextc()) {
                    if (_Traits::eq_int_type(_Traits::eof(), _Meta)) { // end of file, quit
                        _State |= _Istream::eofbit;
                        break;
                    }
                    else if (_Ctype_fac.is(_Ctype::space, _Traits::to_char_type(_Meta))) {
                        break; // whitespace, quit
                    }
                    else { // add character to string
                        _Str.push_back(_Traits::to_char_type(_Meta));
                        changed = true;
                    }
                }
            }
            catch (...) {
                _In.setstate(_Istream::badbit True);
            }
        }

        _In.width(0);
        if (!changed) {
            _State |= _Istream::failbit;
        }
        _In.setstate(_State);

        return _In;
    }

    template <class _Elem, class _Traits, class _SizeT>
    ::std::basic_ostream<_Elem, _Traits>& 
    _Output_string(::std::basic_ostream<_Elem, _Traits>& _Ostr, const _Elem* const _Data, const _SizeT _Size)
    {
        using _Ostream = ::std::basic_ostream<_Elem, _Traits>;
    
        typename _Ostream::iostate _State = _Ostream::goodbit;
        _SizeT _Pad;
        if (_Ostr.width() <= 0 || static_cast<_SizeT>(_Ostr.width()) <= _Size) {
            _Pad = 0;
        }
        else {
            _Pad = static_cast<_SizeT>(_Ostr.width()) - _Size;
        }
    
        const typename _Ostream::sentry _Ok(_Ostr);
    
        if (!_Ok) {
            _State |= _Ostream::badbit;
        }
        else {
            try {
                if ((_Ostr.flags() & _Ostream::adjustfield) != _Ostream::left) {
                    for (; 0 < _Pad; --_Pad) { // pad on left
                        if (_Traits::eq_int_type(_Traits::eof(), _Ostr.rdbuf()->sputc(_Ostr.fill()))) {
                            _State |= _Ostream::badbit; // insertion failed, quit
                            break;
                        }
                    }
                }
    
                if (_State == _Ostream::goodbit
                    && _Ostr.rdbuf()->sputn(
                        _Data, 
                        static_cast<std::streamsize>(_Size)) != static_cast<std::streamsize>(_Size))
                {
                    _State |= _Ostream::badbit;
                }
                else {
                    for (; 0 < _Pad; --_Pad) { // pad on right
                        if (_Traits::eq_int_type(_Traits::eof(), _Ostr.rdbuf()->sputc(_Ostr.fill()))) {
                            _State |= _Ostream::badbit; // insertion failed, quit
                            break;
                        }
                    }
                }
    
                _Ostr.width(0);
            }
            catch (...) {
                _Ostr.setstate(_Ostream::badbit True);
            }
        }
    
        _Ostr.setstate(_State);
        return _Ostr;
    }
    
    template<typename CharType, typename _Traits, typename Alloc>
    ::std::basic_ostream<CharType, _Traits>& operator<<
    (::std::basic_ostream<CharType, _Traits>& _Out, const String<CharType, _Traits, Alloc>& _Str)
    {
        return _Output_string(_Out, _Str.data(), _Str.size());
    }

    template<typename _Elem, typename _Traits, typename Alloc>
    ::std::basic_istream<_Elem, _Traits>& getline
    (::std::basic_istream<_Elem, _Traits>& _In, String<_Elem, _Traits, Alloc>& _Str, const _Elem delim)
    {
        using _Istream = ::std::basic_istream<_Elem, _Traits>;

        typename _Istream::iostate _State = _Istream::goodbit;
        bool _Changed                     = false;
        const typename _Istream::sentry _Ok(_In, true);

        if (_Ok) {
            try {
                _Str.erase();
                const typename _Traits::int_type _Metadelim = _Traits::to_int_type(delim);
                typename _Traits::int_type _Meta = _In.rdbuf()->sgetc();

                for (;; _Meta = _In.rdbuf()->snextc()) {
                    if (_Traits::eq_int_type(_Traits::eof(), _Meta)) { // end of file, quit
                        _State |= _Istream::eofbit;
                        break;
                    }
                    else if (_Traits::eq_int_type(_Meta, _Metadelim)) { // got a delimiter, discard it and quit
                        _Changed = true;
                        _In.rdbuf()->sbumpc();
                        break;
                    }
                    else if (_Str.max_size() <= _Str.size()) { // string too large, quit
                        _State |= _Istream::failbit;
                        break;
                    }
                    else { // got a character, add it to string
                        _Str += _Traits::to_char_type(_Meta);
                        _Changed = true;
                    }
                }
            }
            catch (...) {
                _In.setstate(_Istream::badbit True);
            }
        }

        if (!_Changed) {
            _State |= _Istream::failbit;
        }
        _In.setstate(_State);
        return static_cast<::std::basic_istream<_Elem, _Traits>&>(_In);
    }

    template<typename _Elem, typename _Traits, typename Alloc>
    ::std::basic_istream<_Elem, _Traits>&
    getline(::std::basic_istream<_Elem, _Traits>&& _In, String<_Elem, _Traits, Alloc>& _Str)
    {
        return zuck::getline(_In, _Str, _In.widen('\n'));
    }

    template<typename _Elem, typename _Traits, typename Alloc>
    ::std::basic_istream<_Elem, _Traits>&
    getline(::std::basic_istream<_Elem, _Traits>& _In, String<_Elem, _Traits, Alloc>& _Str)
    {
        return zuck::getline(::zuck::move(_In), _Str, _In.widen('\n'));
    }

    using string    = String<char, ::std::char_traits<char>, zuck::allocator<char>>;
    using wstring   = String<wchar_t, ::std::char_traits<char>, zuck::allocator<wchar_t>>;
    using u16string = String<char16_t, ::std::char_traits<char>, zuck::allocator<char16_t>>;
    using u32string = String<char32_t, ::std::char_traits<char>, zuck::allocator<char32_t>>;
#if _HAS_CXX20
    using u8string  = String<char8_t, zuck::_CharTraits<char8_t>, zuck::allocator<char8_t>>;
#endif
}

